HPAVC/HPAVC CD-ROM.iso/PXDTUT3.ZIP/PXDTUT3.TXT

Text File | 1997-06-01 | 20KB | 547 lines

                  |====================================|
                  |                                    |
                  |   TELEMACHOS proudly presents :    |
                  |                                    |
                  |    Part 3 of the PXD trainers  -   |
                  |                                    |
                  |          3D Vector engine          |
                  |          The basics of 3D          |
                  |                                    |
                  |====================================|

         ___---__-->   The Peroxide Programming Tips   <--__---___

<><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><>


Intoduction
-----------

Hiya... I'm Telemachos of Peroxide - a new danish group (yes... we DO have
groups in Denmark too :)))  )

Since my last trainer quite a few people has mailed me and asked me to do
trainers on various 3D subjects.
As a result of this I have decided to dedicate my next two trainers to the
realm of 3D graphic.

What we'll be doing in the next two trainers is to build a 3D vector engine
capable of doing most of the effects used in todays demos. Our engine will
have the following features.

Tuturial #3 (this one) :
  - Nice 3D object organization - no unnessesary rotations done.
  - Depth sorting
  - Hidden face removal.
  - Solid Fill
  - Glenzing


Tuturial #4 (next week or so...) :
  - Z-shading
  - Flat shading according to moving lightsource(s)
  - Gouraud Shading according to moving lightsource(s)
  - Texturemapping
  - Environment-mapping
  - Phong Shading  (a fake 'cause )


So when you are done with these two tuturials you should be able to to some
nice 3D vector objects.
It might seem that tuturial 4 will be a hard one to get through - but believe
me : We're doing all the preparations in this trainer. Once our 3D engine is
set up all the different shading/fill types are surprisingly alike :)


*************************** ATTENTION ARTISTS!!! *****************************

ARE YOU AN ARTIST ?
DO YOU DRAW VGA-BITMAPS ?
CAN YOU DO GFX IN ALL RESOLUTIONS - 320x200x256 AND VARIOUS SVGA-MODES ?
DO YOU WANT TO SEE YOUR WORK IN AMAZING PRODUCTIONS ?
CAN YOU DO GAME-GFX AS WELL AS BACKGROUNDS FOR DEMOS ?

IF YOU MEET THE ABOVE TERMS (or some at least :) ), THEN DROP ME (TELEMACHOS)
A MESSAGE OR MAIL THE GROUP AT :  [e-mail]

******************************************************************************


If you want to get in contact with me, there are several ways of doing it :

1) Write me via FIDO-net   :      2:235/350.22

2) E-mail me               :      [e-mail]

3) Snail mail me           :      Kasper Fauerby
                                  Saloparken 226
                                  8300 Odder
                                  Denmark

4) Call me  (Voice ! )     :    [phone]


Get this serie from the major demo-related FTP-sites - currently :

  GARBO ARCHIVES  (forgot the address)  :  /pc/programming/

  ftp.teeri.oulu.fi  :   /msdos/programming/docs/


Or grap it from my homepage :

   Telemachos' Codin' Corner   http://www.image.dk/~tm



FIRST THINGS FIRST! - 3D DEFINATIONS AND TRANSLATIONS
------------------------------------------------------

Lets define the 3D space where our object is placed. The origin of the 3D
object space is located at the middle of the screen and the axis is defined
as shown below :

               \ |
              -----------------------------> X-axis
                 | \
                 |   \
                 |     \
                 |       \
                 |         \
                 |           \>
                 |             Z-axis (into the screen :)  )
                 |
                 V
               Y-axis


Ok.. so our object is made from a number of 3D points each defined by (X,Y,Z)
But how do we plot such a 3D point to the screen ?? We must find some way of
translating the 3 coordinated in the 2 coordinates of the screen.
This is done by calculating the intersection between the vector made from the
3D point and the eye position and the viewplane.
I won't get into the math involved in this operation - if you'r interrested go
grap a book on vector math and read the bit about intersection between a line
and a plane.
I'll just give you some formulas :

 X0 := Xofs  +  Round(X*(Zeye/(Zeye-Z)));
 Y0 := Yofs  +  Round(Y*(Zeye/(Zeye-Z)));

Set Xofs to 160 and Yofs to 100 to center object space at the center of the
screen.
If you'r unhappy with these formulas (they are a bit slow because of the
Round and all the floating point muls and divs) you can use a approximation
of the formulas :

 X0 := Xofs + (x div (z-Zoff)) shl 8;
 Y0 := Yofs + (y div (z-Zoff)) shl 8;

This will also work allthough not entirely correct.


LETS TALK ABOUT DATA-STRUCTURES
--------------------------------

Now for the keyword of 3D programming - DATA STRUCTURES !!

In 3D it is VERY important that you think about how to structure your data
so that a minimum of calculations has to be done.
First problem is how to store your 3D object.

The easiest way is to store it an array of polygons, each polygon consisting
of 4 3D points. But it is also the way ONE SHOULD NEVER!! store 3D objects.
Lets have a look at a simple cube. A cube consists of 6 sides right ? And each
side consist of 4 points. That sums up to 24 points to be rotated using the
above mentioned data structure.
But as we all know there is only 8 corners in a cube - ie. there is only 8
DIFFERENT points in a cube.
So what we do is to store all the different points in one array - and then
introduce another variable - we could call it faces - to store information
about which points appears in which faces.
This way we only rotates ONE THIRD of the points we rotate using the first
methode.
The goal in 3D is never do do unnessesary calculations. Only rotate each point
ONCE, only draw each pixel on the screen ONCE and so on.

Now some words about precision.
As we are using a pretty low resolution (320X200) a fairly big amount of
rounding is performed when rotation / projecting a 3D point. If you store your
3D object in a single variable and rotates the object into the very same
variable the object will in time be distorted from the roundings. So my advice
is to store the original 3D object in ONE variable and then rotate this
BASEOBJECT into a buffer from which you then perform all the calculations on
the rotated 3D object. This way each rotation starts out with a "fresh" 3D
object and the distortion will be minimal.


For an idea of a 3D data structure check out the sample program supplied with
this text.
NOTE!!
This is only meant as an idea of a data structure. Modify it to match your
needs.



OK - NOW I WANT TO ROTATE THE POINTS
-------------------------------------

Having an object defined by 3D coords is no fun if it just stands still on
the screen. So we want to rotate it around the different axes.

For this there is 3 formulas - one for each axis. Please note that the
formulas presented here is the standard rotation formulas given by vector math
books. Numerous optimizations has been made to these routines making rotation
a little faster but I won't get into that in this text. For now the important
thing is to make the points rotate correctly :)
Before we throw ourselves into the formulas one more important note has to
be made. One has to bear in mind that the sequence in which the point is
rotated around the different axes DOES matter. To rotate the point 5 degrees
around the X axis and then 5 degrees around the Y axis is NOT the same as
rotating it about the Y axis and then the X axis!! Think about it!
So, it has been decided that one rotates around the axes in the following
order :  X, Y and then Z.

Ok... now it's time for the formulas :

rotation around Z-axis :  (rotating the point X,Y,Z  A degrees)
    Xrotated = Cos (A)*X - Sin (A)*Y
    Yrotated = Sin (A)*X + Cos (A)*Y
    Zrotated = Z

rotation around X-axis :
    Xrotated = X
    Yrotated = Cos (A)*Y - Sin (A)*Z
    Zrotated = Sin (A)*Y + Cos (A)*Z

rotation around Y-axis :
    Xrotated = Cos (A)*X - Sin (A)*Z
    Yrotated = Y
    Zrotated = Sin (A)*X + Cos (A)*Z

OK... these are the formulas - check out the sample program for an idea of
how to combine them in a pretty fast way.
I just grapped the rotation routine from an Asphyxia tuturial by Denthor.
His routine is a straight implemention of the above mentioned formulas -
in fixed point assembler. Thanx Denthor.


OK.. lets sum things up.
By now we have learned to
  - rotate a 3D point around all 3 axis
  - Translate a 3D point into 2D screen coordinates

This is allmost enough to get you started coding a 3D object engine. With
this information you could easily code a wirefram engine - as a matter of
fact I suggest you do just that! By coding a simple 3D engine you really learn
the next stuff faster :)


BACK SO SOON ??? - POLYGON DRAWING
-----------------------------------

OK.. I guess you have now coded a wireframe engine (not so hard ehh ??) and
you want more. Lets face it - your demo won't win The Party if it's only
running wireframe 3D graphics.
But we're going to change that - now is the time for solid objects!! (WEE!!)
To draw a solid face we need to code a good polygon routine. We'll code it in
a way so that all the nice shadings in the next tuturial will be really easy
to implement - I'll tell you how right now!

What is a polygon ?? In demos most polygons are triangles but today we'll draw
four sided polygons because I'm gonna use a simple square box for my sample
code. Don't worry though - I'll tell you how to do triangles too.
So we got our four points and we want to fill the shape with some color.
But how ?? Well... we draw polygons scanline per scanline. Ie. a polygon is a
bunch of horizontal lines.
So the first thing we'll need is a horizontal line drawer :


Procedure HorLine(Xbegin, Xend,Ypos : integer;color : byte;where : word);
Assembler;
asm
 mov cx,[Xend]
 inc cx
 sub cx,[Xbegin]   {cx = length of line - used for counter }
                   {note, I assume that Xbegin < Xend - the poly routine}
                   {will take care of that...}
 mov ax,[ypos]
 shl ax,8
 mov di,ax
 shr ax,2
 add di,ax
 add di,[Xbegin]   {di = Ypos * 320 + Xbegin - offset for our line}
 mov es,[where]    {where to draw..}

 mov al,[color]
 rep stosb         {I draw byte by byte - slower than drawing a word at a}
                   {time but it is because of the changes we are going to}
                   {make to this routine when glenzing/gouraud/texturemapping}
end;



OK.. now we just have to find out what the X-coords for each scanline is.
We define a variable to hold that information for us :

     polygon : Array[0..199,1..2] of byte;

This variable can hold the endpoints of a horizontal line for each of the 200
y-lines on the VGA screen.

Now we want to fill this buffer out with the correct information. For each of
the four sides (three if it were a triangle) we scan along the edge of the
polygon and updates the polygon variable like this :

Procedure ScanPolySide(X1,Y1,X2,Y2 : integer);
var
 DeltaX : integer;
 temp : integer;
 Xposfixed,Xpos : integer;
 counter : integer;
begin
  if Y2=Y1 then exit;          {exit if side is a horizontal line }
  if (Y2<Y1) then              {make sure Y1 is top point}
               begin
                 temp := Y1;
                 Y1 := Y2;
                 Y2 := temp;

                 temp := X1;
                 X1 := X2;
                 X2 := temp;   {switch the points if Y1 is not top..}
               end;

  DeltaX := ((X2-X1) shl 7) div (Y2-Y1); {DeltaX in 9.7 fixed point math}
  Xposfixed := X1 shl 7; {Xpos in 9.7 fixed point math }
    for counter := Y1 to Y2 do
         begin
           Xpos := XposFixed shr 7;
           if (Xpos < polygon[counter,1]) then polygon[counter,1] := Xpos;
           if (Xpos > polygon[counter,2]) then polygon[counter,2] := Xpos;
           Xposfixed := XposFixed + DeltaX;
         end;
end;


Now... run this procedure on each side of the poly, and the variable 'polygon'
is set up and ready for our friend Mr. Horline.


So..

Procedure Polygon(X1,Y1,X2,Y2,X3,Y3,X4,Y4 : integer;color : byte; where : word);
var
 counter : integer;
 Ymin, Ymax : integer;
 polygon : Array[0..199,1..2] of integer;

begin
 Ymin := Y1;
 Ymax := Y1;
 if (Y2 < Ymin) then Ymin := Y2;
 if (Y2 > Ymax) then Ymax := Y2;
 if (Y3 < Ymin) then Ymin := Y3;
 if (Y3 > Ymax) then Ymax := Y3;
 if (Y4 < Ymin) then Ymin := Y4;
 if (Y4 > Ymax) then Ymax := Y4;  {what is Ymin and Ymax in this polygon ?}

 for counter := 0 to 199 do
   begin
     polygon[counter,1] := 32000;
     polygon[counter,2] := -32000;
   end;

 {we have to initialize our variable 'polygon' to some extreme values}

 ScanPolySide(X1,Y1,X2,Y2);
 ScanPolySide(X2,Y2,X3,Y3);
 ScanPolySide(X3,Y3,X4,Y4);
 ScanPolySide(X4,Y4,X1,Y1); {all four sides scanned}

 for counter := Ymin to Ymax do
    Horline(polygon[counter,1],polygon[counter,2],counter,color,where);
end;

Well... that was pretty easy... Now we can do solid sides in our 3D cube.
Try it out before continuing :)



WHAT - SOMETHING IS WRONG ??  - DEPTH SORTING :
------------------------------------------------

YES - I know. You have some problems getting your cube look right when having
different colors for each face. This is because of the random order we draw
the faces in.
We have to find some way of depth sorting them. We sort the faces by their
center point. The Z component of their center point, that is.
So for each frame we have to calculate the center Z-value for each face in the
object.
To find the center Z value we add the Z values from the 4 points making the
face and divide this value by 4 (if we are talking triangles obviously we'll
divide by 3)
Only that we don't divide at all! If we don't divide by the number of points
we'll NOT end up with the center Z value. We'll end up with a value that is
4 times to big. But as ALL the calculated Z values will be 4 times to big
they will still sort corectly.

We'll store the values in a variable called

     centers : Array[1..Num_of_faces]  of integer;

But when we start sorting this table we'll mess up which center that belongs
to which face. To solve this problem we'll introduce another variable called

    OrderTable  :  Array[1..Num_of_faces] of integer;

This table will store the correct sequence for drawing the faces. Ie. it'll
store the face-numbers belonging to a centervalue.

To do the actual sorting we'll use a simple bubble-sort. This is a pretty
simple sorting algoritm which will work for us as long we are not talking
sorting hundreds of faces. If you are rendering LOTS of faces I suggest you
use a quicksort routine instead.
The idea is to scan through the centers variable and compare the entries
two and two. If the value at position+1 is higher than the value at position
we switch the two values and updates the ordertable variable.
We then reset the scan and start over. We continue doing this until we reach
the end of 'centers' without having to switch any values.


Procedure Sort_faces;
{Just a simple bubble-sort - not to fast but what the heck :) }
{Faces with the HIGHEST Z-val is placed first in Order[] }
VAR
  counter : integer;
  position : integer;
  tempval : integer;
BEGIN
  for counter:=1 to Num_of_faces do BEGIN
    OrderTable[counter]:=counter;
  END;
  {we resets the ordertable so that it matches the unsorted 'centers' variable}
  position := 1;

  repeat
    if (centers[position] < centers[position+1]) then
        BEGIN
          tempval := Centers[position+1];
          Centers[position+1] := centers[position];
          centers[position] := tempval;

          tempval := OrderTable[position+1];
          OrderTable[position+1] := OrderTable[position];
          OrderTable[position] := tempval;

          position:=1;
        END;
      inc(position);
  until (position = Num_of_faces);
END;


Now when doing the faces we draw them in the order specified in OrderTable.
Go ahead... try it out...



HIDDEN FACE REMOVAL
--------------------

Fire up your 3D engine and take a look at the rotating cube.
Looks cool ehh ?? Nice work... YOU did that ;)
But try and count the faces visible at a time. How many faces do you see at
one time ? Only about half of them ????
ARGH!!  We are drawing half an object that is never seen ???
This won't do. Right now it does not matter much as drawing a polygon is fairly
fast - but next week when we start texturemapping or shading the faces it will
slow things down.
So - we'll just have to remove the faces we do not see. This is fortunately
VERY!! easy.
To be able to perform this operation it is important that you have defined
your faces in a clockwise direction. Ie. all faces should be defined as :


                   P1               P2
                    |---------------|
                    |               |
                    |               |
                    |               |
                    |               |
                    |               |
                    |---------------|
                   P4               P3


Ok... now I'll introduce a new formula to you - the cross product. The cross
product is a formula that returns the normal to a plane :

        Xnormal=(P2.Y-P1.Y)(P1.Z-P3.Z)-(P2.Z-P1.Z)(P1.Y-P3.Y)
        Ynormal=(P2.Z-P1.Z)(P1.X-P3.X)-(P2.X-P1.X)(P1.Z-P3.Z)

        Znormal=(P2.X-P1.X)(P1.Y-P3.Y)-(P2.Y-P1.Y)(P1.X-P3.X)

Well... for now we are only interrested in the Z normal. If the Z normal is
negative it means that the normal points towards us - ie. we draw the face.
If not we discard it.

One more important note to make is that because the Znormal does not involve
any Z components of the points we can use it on the PROJECTED 2D values.

Now go implement this in your 3D engine - if you are having trouble take a
look at the sample program.
Next week we'll see how we use this normal (the hole 3D normal though) for
shading...



ONE LAST THING - GLENZING THE POLYGON
--------------------------------------

OK.. now we have done a 3D object engine that handles 3D objects correct -
showing only what HAS to be shown.
That done I think you are ready for another kind of fill - that TOTALLY
ignores ALL we have learned about sorting and hidden face removal... SIGH,
thats life :)

The effect is called glenzing and the idea is to make the object look like it
is made from colored glass. This effect is done by setting the correct
pallette. I don't think there is any way of calculating this pallette so you'll
have to experiment.
Now when drawing your faces you do not draw the polygon in one color. For each
pixel you grap the background color and add it to the face color.
This is of course a little slower than doing single colored polygons but not
much. You'll have to change your horizontal line drawer to do this - check
the sample program if you experiment any trouble.

When glenzing you should obviously NOT remove the faces pointing away from
you as they can be seen through the glass sides.
Sorting is useless.... the result will look the same with or without sorting.
In my opinion glenzing is not a cool effect - but well... it can't hurt to
know how to do it :)



LAST REMARKS
-------------

Well, that's about all for now.
Hope you found this doc useful - and BTW : If you DO make anything public using
these techniques please mention me in your greets or where ever you se fit.
I DO love to see my name in a greeting :=)


As mentioned earlier my next tuturial will be on different types of shading -
using this 3D object engine as a base...
But after that ??
If you have any good ideas for a subject you wish to see a tuturial on please
mail me. If I like the idea (and know anything about it :)  ) I'll write a
tut on it.

Keep on coding...

Telemachos - May '97.